/*
https://leetcode.cn/problems/numbers-with-repeated-digits/submissions/568223608/
*/
class Solution {
public:
    int numDupDigitsAtMostN(int n) {
        //将数字n转为字符串
        string s = to_string(n);
        //数字n有多少位（既n是几位数）
        int m = s.length();
        //用于记忆化，可以减少计算量
        vector<vector<int>> memo(m, vector<int>(1 << 10, -1)); // -1 表示没有计算过

        //递归函数
        auto dfs = [&](auto&& dfs, int i, int mask, bool is_limit, bool is_num) -> int {
            //如果是n的最后一位数
            if (i == m) {       
                return is_num; // is_num 为 true 表示得到了一个合法数字
            }

            //没有受到限制 并且 没有前导0 并且之前算过了
            if (!is_limit && is_num && memo[i][mask] != -1) {
                return memo[i][mask];   //算过了就直接将它返回
            }
            //res存储答案
            int res = 0;

            /*
            假如“010” 此时i==0
            因为有前导0,数字不合法，所以我们跳过i==0，直接看i==1的情况
            在 res = dfs(dfs, i + 1, mask, false, false); 中
            i+1就是看下一位，mask就是已出现过的数字的集合
            第一个false是 is_limit ，因为我们第i位没有填，所以没有受到限制
            第二个false是 is_num，因为我们第i位没有填，所以对于第i+1位来说,它前面是没有数字的,所以也是false 
            */
            if (!is_num) { // 可以跳过当前数位
                res = dfs(dfs, i + 1, mask, false, false);
            }

            // 如果前面填的数字都和 n 的一样，那么这一位至多填数字 s[i]（否则就超过 n 啦）
            int up = is_limit ? s[i] - '0' : 9;

            // 枚举要填入的数字 d
            // 如果前面没有填数字，则必须从 1 开始（因为不能有前导零）
            int d = is_num ? 0 : 1;
            for (; d <= up; d++) {
                // d 不在 mask 中，说明之前没有填过 d
                if ((mask >> d & 1) == 0) {   //成立，我们就将d填入第i位
                /*
                mask|(1<<d) 1左移d次，与mask进行'|'运算，将d存入集合中
                is_limit为true时，up为s[i]-'0'：
                    d<up时,  "is_limit && d == up" 为false，表示接下来的递归你可以填任意一个数；
                    d==up时, "is_limit && d == up" 为true，表示接下来的递归你填的数会受到限制；
                is_limit为false时，up为9：
                    d<9时,  "is_limit && d == 9" 为false，表示接下来的递归你可以填任意一个数；
                    d==9时, "is_limit && d == 9" 为true，表示接下来的递归你填的数会受到限制；
                由于我们将d填入第i位了，所以is_num为true，表示我前面已经填过数字了
                */
                    res += dfs(dfs, i + 1, mask | (1 << d), is_limit && d == up, true);
                }
            }
            /*
            如果第i位数的前面已经填过数字了（is_num）接下来填的数没有限制(!is_limit)
            说明我们填到第i位的数字，用了集合mask里面的数字，得到的情况有res个
            就是字符串s[0]到s[i]，我用集合里面的数，通过排列组合得到满足要求的组合的数量总共有res个 
            我们就可以用memo数组存储起来，减少计算量 */
            if (!is_limit && is_num) {
                memo[i][mask] = res; // 记忆化
            }
            cout<<i<<" "<<res<<endl;
            //将递归得到的答案返回
            return res;
        };
        /*
        第1个0代表：我们从字符串s的第0位数开始递归
        第2个0代表：我们的集合一开始是空的
        true代表：我们第一次递归，是受限制的
        false代表：我们第一次递归，前面的没有填过数字
        */
        return n-dfs(dfs, 0, 0, true, false);
    }
};